//
// Created by mac on 2023/11/20.
//

// 三数之和
#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    vector<vector<int> > threeSum(vector<int>& nums)
    {
        // 1、建表
        int n = nums.size();
        vector<vector<int> > ret;
        // 2、排序
        sort(nums.begin(), nums.end());
        // 3、使用数指针解决问题
        int i = 0;
        while(i < n - 2)
        {
            int target = -nums[i];
            int left = i + 1, right = nv - 1;
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum < target) ++left;
                else if(sum > target) --right;
                else
                {
                    vector<int> tmp;
                    tmp.push_back(nums[i]);
                    tmp.push_back(nums[left]);
                    tmp.push_back(nums[right]);
                    ret.push_back(tmp);
                    while(left + 1 < right && nums[left + 1] == nums[left]) ++left;
                    while(right - 1 > left && nums[right - 1] == nums[right]) --right;
                }
                ++left, --right;
            }
            while(i + 1 < n - 2 && nums[i + 1] == nums[i]) ++i;
            ++i;
        }
        return ret;
    }
};

int main()
{
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(-1);
    nums.push_back(-1);
    nums.push_back(0);
    Solution tmp;
    tmp.threeSum(nums);
    cout << "hello world" <<endl;
    return 0;
}

// 四数之和
class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        // 1、初始化
        int n = nums.size();
        vector< vector<int> > ret;
        // 2、排序
        sort(nums.begin(), nums.end());
        // 3、依次固定一个数，然后使用“三数之和”解决问题
        for(int i = 0; i < n - 3;)
        {
            // 4、再依次固定一个数，然后使用“双指针”解决问题
            for(int j = i + 1; j < n - 2;)
            {
                int left = j + 1, right = n - 1;
                double aim = (double)target - nums[i] - nums[j];
                // 5、双指针算法找到两数之和等于 aim 的元素
                while(left < right)
                {
                    double sum = nums[left] + nums[right];
                    if(sum < aim) ++left;
                    else if(sum > aim) --right;
                    else
                    {
                        ret.push_back( {nums[i], nums[j], nums[left], nums[right]} );
                        ++left, --right; // 保证 left、right 选择的元素不漏
                        // 对 left、right 已经选择过的元素去重
                        while(left < right && nums[left] == nums[left - 1]) ++left;
                        while(left < right && nums[right] == nums[right + 1]) --right;
                    }
                }
                // 保证 j 选择的元素不漏
                ++j;
                // 对 j 已经选择过的元素去重
                while(j < n - 2 && nums[j] == nums[j - 1]) ++j;
            }
            // 保证 i 选择的元素不漏
            ++i;
            // 对 i 已经选择过的元素去重
            while(i < n - 3 && nums[i] == nums[i - 1]) ++i;
        }
        // 6、返回最终结果
        return ret;
    }
};
/*
- 时间复杂度：O(n^3)
- 空间复杂度：O(1)
*/
